package algorithm_demo.demo_advanced;

/**
 * 字符串匹配问题
 * 正常的暴力解时间复杂度为O(N*M)
 * KMP解O(N)
 * @author Api
 * @date 2023/3/30 0:22
 */
public class Code11_KMP {


    public static int getIndexOf(String s, String m){
        if (s == null || m == null || m.length()<1 || s.length()<m.length()){
            return -1;
        }
        char[] str = s.toCharArray();
        char[] match = m.toCharArray();
        int x = 0;//str中当前比对到的位置
        int y = 0;//match中当前比对到的位置
        int[] next = getNextArray(match);//next[i] match中i之前的字符串match[0..i-1]
        while(x< str.length && y < match.length){
            if (str[x] == match[y]){
                x++;
                y++;
            }else if (next[y] == -1){//y=0位置或者写y==0也可以】
                x++;
            }else{
                y = next[y];
            }
        }
        //1. x越界了，y没有越界 返回-1
        //2. x没越界，y越界了 ？
        //3.
        return y == match.length? x-y :-1;
    }

    public static int[] getNextArray(char[] match){
        if (match.length == 1){
            return new int[]{-1};
        }
        int[] next = new int[match.length];
        next[0] = -1;//人为规定
        next[1] = 0;//人为规定
        int i = 2;
        //cn代表，cn位置的字符，是当前和i-1位置比较的字符
        int cn = 0;
        while(i < next.length){
            if (match[i-1] == match[cn]){//跳出来的时候
                next[i++] = ++cn;
            }else if (cn>0){
                cn = next[cn];
            }else{
                next[i++] = 0;
            }
        }
        return next;
    }
}
